package com.example.demo.java.container.map;

/**
 * 理解HashMap  JDK1.8
 * 不要死记，根据源码读一遍，其实就相当于我们自己封装一个工具类，不过人家写的规范且完善 O(∩_∩)O
 *  第一步：知道都有什么方法，一步一步的意义
 *  第二步：为什么要这么做
 *  第三步：写代码时想想HashMap的原理，应用
 * 有一篇特别详细的文章，推荐（光看死记是没用的，一定要理解 = 写代码 + 写代码 + 写代码 + .......）
 * https://blog.csdn.net/qq_31821675/article/details/105000051?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-3&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-3
 *
 * Hashmap的结构，1.7和1.8有哪些区别详细讲解
 *  https://blog.csdn.net/lovezhaohaimig/article/details/86595113?ops_request_misc=&request_id=&biz_id=102&utm_source=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-1
 */
public class UDHashMap {

    /** 1、HashMap 问题梳理 (带着问题去看) */
        // (1) HashMap的数据结构？HashMap底层存储结构？直接采用红黑树不行么？红黑树的实现原理？
        // (2) HashMap底层是如何实现的？HashMap的数据插入原理？HashMap数据的获取？
        // (3) HashMap怎么设定初始容量大小？初始值为什么是16？
        // (4) HashMap的长度为什么是2的倍数？HashMap的哈希函数怎么设计的，为什么？
        // (5) HashMap时一般使用什么类型的元素作为Key？为什么？
        // (6) 自定义的class作为HashMap的key该如何实现？
        // (7) HashMap采用了什么方法解决Hash冲突？
        // (8) 链表转红黑树是链表长度达到阈值，这个阈值是多少？为什么？
        // (9) HashMap JDK1.8 做了哪些优化，为什么？1.7和1.8有哪些区别?
        // (10) JDK1.8以后为什么改用尾插法？
        // (11) HashMap是线程安全的吗，哪里会导致不安全？
        // (12) 怎么解决这个线程不安全的问题，为什么线程安全？
        // (13) HashMap内部节点是有序的吗？
        // (14) 有没有有序的Map？
        // (15) LinkedHashMap怎么实现有序的？
        // (16) TreeMap怎么实现有序的？
    /** 2、源码梳理，读源码，反复读，下面的代码就是HashMap的源码 */
    /** 3、再去想问题，结合源码，理解HashMap */



    /**
     * 一、数据结构：处理hash冲突的链表和红黑树以及位桶
     */

        /** 1、链表的实现(部分代码) */
            //    static class Node<K, V> implements Map.Entry<K, V> {
                      /** Node是单向链表，它实现了Map.Entry接口 */
            //        final int hash;   // hash值
            //        final K key;      // key值
            //        V value;          // key对应的value
                      /** 当hash冲突，但key值不同时，链式存储冲突的Node */
            //        HashMap.Node<K, V> next;
            //        // 构造函数Hash值 键 值 下一个节点
            //        Node(int hash, K key, V value, HashMap.Node<K, V> next) {
            //            this.hash = hash;
            //            this.key = key;
            //            this.value = value;
            //            this.next = next;
            //        }
            //    }

        /** 2、红黑树(部分代码) */
            /** 红黑树详解：了解位置，记住最好 http://www.tianxiaobo.com/2018/01/11/%E7%BA%A2%E9%BB%91%E6%A0%91%E8%AF%A6%E7%BB%86%E5%88%86%E6%9E%90/ */
            /*
            在JDK1.6，JDK1.7中，HashMap采用位桶+链表实现，即使用链表处理冲突，
                同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，
                即hash值相等的元素较多时，通过key值依次查找的效率较低。
            而JDK1.8中，HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值（8）时，
                将链表转换为红黑树，这样大大减少了查找时间。在jdk1.8版本后，java对HashMap做了改进，
                在链表长度大于8的时候，将后面的数据存在红黑树中，以加快检索速度。

            JDK1.8HashMap的红黑树是这样解决的：
                如果某个桶中的记录过大的话（当前是TREEIFY_THRESHOLD = 8），
                HashMap会动态的使用一个专门的treemap实现来替换掉它。
                这样做的结果会更好，是O(logn)，而不是糟糕的O(n)。

                它是如何工作的？
                    前面产生冲突的那些KEY对应的记录只是简单的追加到一个链表后面，
                    这些记录只能通过遍历来进行查找。但是超过这个阈值后HashMap开始将列表升级成一个二叉树，
                    使用哈希值作为树的分支变量，如果两个哈希值不等，但指向同一个桶的话，较大的那个会插入到右子树里。
                    如果哈希值相等，HashMap希望key值最好是实现了Comparable接口的，这样它可以按照顺序来进行插入。
                    这对HashMap的key来说并不是必须的，不过如果实现了当然最好。
                    如果没有实现这个接口，在出现严重的哈希碰撞的时候，你就并别指望能获得性能提升了。

                为什么是红黑树？为什么不直接采用红黑树还要用链表？
                    因为红黑树需要进行左旋，右旋操作， 而单链表不需要，
                    如果元素小于8个，查询成本高，新增成本低
                    如果元素大于8个，查询成本低，新增成本高

            红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
                性质1. 节点是红色或黑色。
                性质2. 根节点是黑色。
                性质3 每个叶节点（NIL节点，空节点）是黑色的。
                性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
                性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
                         */
            //    static final class TreeNode<k,v> extends LinkedHashMap.Entry<k,v> {
            //        TreeNode<k,v> parent;  // 父节点
            //        TreeNode<k,v> left;    // 左子树
            //        TreeNode<k,v> right;   // 右子树
            //        TreeNode<k,v> prev;    // 上一个同级节点
            //        boolean red;           // 颜色属性
            //        TreeNode(int hash, K key, V val, Node<k,v> next) {
            //            super(hash, key, val, next);
            //        }
            //        //返回当前节点的根节点
            //        final TreeNode<k,v> root() {
            //            for (TreeNode<k,v> r = this, p;;) {
            //                if ((p = r.parent) == null)
            //                    return r;
            //                r = p;
            //            }
            //        }
            //    }

        /** 3、位桶 */
            // transient Node<k,v>[] table;//存储（位桶-bucket）的数组 （哈希桶数组）

        /** 小结： */
            /* 首先有一个每个元素都是链表（可能表述不准确）的数组，当添加一个元素（key-value）时，
                就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，
                这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，所以说数组存放的是链表。
                而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。 */

    /**
     * 二、HashMap源码分析
     */

        /** 1、类的继承关系 */
            // public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
            /* 可以看到HashMap继承自父类（AbstractMap），实现了Map、Cloneable、Serializable接口。
                其中，Map接口定义了一组通用的操作；Cloneable接口则表示可以进行拷贝，
                在HashMap中，实现的是浅层次拷贝，即对拷贝对象的改变会影响被拷贝的对象；
                Serializable接口表示HashMap实现了序列化，即可以将HashMap对象保存至本地，之后可以恢复状态。 */

        /** 2、类的属性 用transient关键字标记的成员变量不参与序列化过程 */
            //    static final int DEFAULT_INITIAL_CAPACITY = 16;                     // 初始容量，默认16(容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。)
            //    static final int MAXIMUM_CAPACITY = 1073741824;                     // 容量的最大值
            //    static final float DEFAULT_LOAD_FACTOR = 0.75F;
                                                                                      /* 填充因子0.75,填充因子是哈希表在其容量自动扩容之前可以达到多满的一种度量。
                                                                                          当哈希表中的条目数超出了加载因子与当前容量的乘积时，
                                                                                          则要对该哈希表进行扩容、rehash操作（即重建内部数据结构），
                                                                                          扩容后的哈希表将具有两倍的原容量。*/
            //    static final int TREEIFY_THRESHOLD = 8;
                                                                                      /* 当哈希桶数组内节点数大于8时，
                                                                                          通过treeifyBin方法中判断长度是否大于最小红黑树容量64,
                                                                                          小于则继续扩容，大于则转为红黑树。*/
            //    static final int UNTREEIFY_THRESHOLD = 6;                           // 当哈希桶数组内节点数小于6时，数据存储结构变为数组+链表
            //    static final int MIN_TREEIFY_CAPACITY = 64;                         // 哈希桶数组的长度，默认64
            //    transient HashMap.Node<K, V>[] table;                               // 哈希桶数组，存储Node节点
            //    transient Set<Map.Entry<K, V>> entrySet;                            // 存储Map的节点信息，遍历时强烈推荐使用
            //    transient Node<k,v>[] table;                                        // 存储元素的数组，总是2的幂次倍
            //    transient Set<map.entry<k,v>> entrySet;                             // 存放具体元素的集
            //    transient int size;                                                 // 存放元素的个数，注意这个不等于数组的长度。
            //    transient int modCount;                                             // 每次扩容和更改map结构的计数器
            //    int threshold;                                                      // 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
            //    final float loadFactor;                                             // 加载因子

        /** 3、类的构造函数 */

            /** (1) HashMap(初始容量, 加载因子)型构造函数 */
                //    public HashMap(int initialCapacity, float loadFactor) {
                          /** 初始容量不能小于0，否则报错 */
                //        if (initialCapacity < 0)
                //            throw new IllegalArgumentException("Illegal initial capacity: " +
                //                    initialCapacity);
                          /** 初始容量不能大于最大值，否则为最大值 */
                //        if (initialCapacity > MAXIMUM_CAPACITY)
                //            initialCapacity = MAXIMUM_CAPACITY;
                          /** 填充因子不能小于或等于0，不能为非数字 */
                //        if (loadFactor <= 0 || Float.isNaN(loadFactor))
                //            throw new IllegalArgumentException("Illegal load factor: " +
                //                    loadFactor);
                          /** 初始化填充因子 */
                //        this.loadFactor = loadFactor;
                          /** 初始化threshold大小，tableSizeFor(initialCapacity)返回大于initialCapacity的最小的二次幂数值。 */
                //        this.threshold = tableSizeFor(initialCapacity);
                //    }

            /** (2) HashMap(Map<? extends K>)型构造函数 */
                //    public HashMap(Map<? extends K, ? extends V> m) {
                //        // 初始化填充因子
                //        this.loadFactor = DEFAULT_LOAD_FACTOR;
                //        // 将m中的所有元素添加至HashMap中
                //        putMapEntries(m, false);
                //    }

                //    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
                //        int s = m.size();
                //        if (s > 0) {
                              /** 判断table是否已经初始化 */
                //            if (table == null) { // pre-size
                                  /** 未初始化，s为m的实际元素个数 */
                //                float ft = ((float)s / loadFactor) + 1.0F;
                //                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                //                        (int)ft : MAXIMUM_CAPACITY);
                                  /** 计算得到的t大于阈值，则初始化阈值 */
                //                if (t > threshold)
                //                    threshold = tableSizeFor(t);
                //            }
                              /** 已初始化，并且m元素个数大于阈值，进行扩容处理 */
                //            else if (s > threshold)
                //                resize();
                              /** 将m中的所有元素添加至HashMap中 */
                //            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                //                K key = e.getKey();
                //                V value = e.getValue();
                //                putVal(hash(key), key, value, false, evict);
                //            }
                //        }
                //    }

        /** 4、hash算法 */
            static final int hash(Object key) {
                int h;
                /** hash值算法(扰动函数)：哈希值的低16位与其高16位进行异或 */
                return key == null ? 0 : (h = key.hashCode()) ^ h >>> 16;
            }
            /* 在putVal源码中，我们通过(n-1)&hash获取该对象的键在HashMap中的位置。
                （其中hash的值就是hash()的返回值）其中n表示的是hash桶数组的长度，
                并且该长度为2的n次方，这样(n-1)&hash就等价于hash%n。因为&运算的效率高于%运算。 */
                //    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                //                   boolean evict) {
                //        if ((p = tab[i = (n - 1) & hash]) == null) //获取位置
                //            tab[i] = newNode(hash, key, value, null);
                //    }

            /** ① 哈希值的计算为什么设置成扰动函数？为什么低16位与其高16位做异或操作？ */
            /*
                为什么这么做？
                    当数组长度n较小时，n-1的二进制数高16位全部为0，这个时候如果直接和h值进行&（按位与）操作，
                    那么只能利用到h值的低16位数据，这个时候会大大增加hash冲突发生的可能性，
                    因为不同的h值转化为2进制后低16位是有可能相同的，
                    如：一个h1 = 3654061296 ，另一个h2 = 3652881648，但是不幸的是这h1、h2两个数转化为2进制后低16位是完全相同的，
                    所以h1 & (n-1)和 h2 & (n-1) 会计算出相同的结果，
                    这也导致了node1和node2 存储在了数组索引相同的位置，发生了hash冲突。

                如何解决？
    ​	            当我们使用进行 h ^ (h >>> 16) 操作时，会将h的高16位数据和低16位数据进行异或操作，
                    所以即使h1和h2的低16位相同，最终计算出的hash值低16位也大概率是不同的，降低了hash冲突发生的概率。
             */

            /** ② 在存储数据时，计算索引位置，为什么使用 (n-1)&hash？ 注：n为数组长度 */
            /*
                为什么是n-1?
                    HashMap规定了数组的长度n必须为2的整数次幂，既然n为2的整数次幂，
                    那么n一定是一个偶数。那么我们来比较i = hash & n和 i = hash & (n-1)有什么异同。

                    n为偶数，那么n转化为2进制后最低位一定为0，与hash进行按位与操作后最低位仍一定为0，
                        这就导致i值只能为偶数，这样就浪费了数组中索引为奇数的空间，同时也增加了hash冲突发生的概率。

                    所以我们要执行n-1,得到一个奇数，这样n-1转化为二进制后低位一定为1，
                        与hash进行按位与操作后最低位即可能位0也可能位1，这就是使得i值即可能为偶数，也可能为奇数，
                        充分利用了数组的空间，降低hash冲突发生的概率。
             */

            /** ③ HashMap规定了数组的长度n必须为2的整数次幂，为什么？resize() */
            /*
                以链表形式存在的节点:
                    存在两个数他们的 Hash 值分别为：5，21 二进制形式分别为（0101，10101）。
                    若没有进行扩容时容量为 16，进行扩容之后的容量为 32
                    坐标点的计算（计算规则 ：e.hash & (newCap - 1)）:

                        没有进行扩容时：
                            15 | 0000 1111
                            5  | 0000 0101  &(与15进行位与操作)  =  0000 0101  =  5
                            21 | 0001 0101  &(与15进行位与操作)  =  0000 0101  =  5
                            可以看到hash冲突，会追加至同一链表的末端

                        进行扩容之后：
                            31 | 0001 1111
                            5  | 0000 0101  &(与31进行位与操作)  =  0000 0101  =  5
                            21 | 0001 0101  &(与31进行位与操作)  =  0001 0101  =  21(正好增加了oldCap)

                        扩容时，坐标点的更新（计算规则 ： e.hash & oldCap）：
                            16 | 0001 0000
                            5  | 0000 0101  &(与16进行位与操作)  =  0000 0000 == 0 (此时坐标不变)
                            21 | 0001 0101  &(与16进行位与操作)  =  0001 0000 != 0 (此时坐标为原坐标+oldCap)

                        总结：
                            可以看出，每次扩容两倍，其实就是左侧多个1，计算规则（newCap - 1）
                            容量(16) 15 ：0000 1111
                            容量(32) 31 ：0001 1111
                            容量(64) 63 ：0011 1111
                            此时再与已存储的hash进行位与操作，如果是0，坐标不变，如果是1，坐标加上oldCap,进一步降低hash冲突发生的概率。
             */

            /** 扩展：key.hashCode方法 */
                /*
                    大家都知道，计算机的乘法涉及到移位计算。
                    当一个数乘以2时，就直接拿该数左移一位即可！选择31原因是因为31是一个质数！
                    所谓质数是指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。
                    在存储数据计算hash地址的时候，我们希望尽量减少有同样的hash地址，所谓“冲突”。
                    如果使用相同hash地址的数据过多，那么这些数据所组成的hash链就更长，从而降低了查询效率！
                    所以在选择系数的时候要选择尽量长(31 = 11111[2])的系数并且让乘法尽量不要溢出
                    (如果选择大于11111的数，很容易溢出)的系数，因为如果计算出来的hash地址越大，所谓的“冲突”就越少，查找起来效率也会提高。
                    31的乘法可以由i*31== (i<<5)-1来表示，现在很多虚拟机里面都有做相关优化，
                    使用31的原因可能是为了更好的分配hash地址，并且31只占用5bits！
                    在java乘法中如果数字相乘过大会导致溢出的问题，从而导致数据的丢失.
                    而31则是素数（质数）而且不是很长的数字，最终它被选择为相乘的系数。
                 */

        /**
         * =========================================5.重要方法分析=========================================
         * (1)、获取数据  get -> getNode
         * (2)、存储数据  put -> putVal
         * (3)、扩容方法  resize
         * (4)、删除数据  remove -> removeNode
         */

            /**
             * (1)、获取数据  get -> getNode
             */
                //    public V get(Object key) {
                //        Node<K,V> e;
                //        return (e = getNode(hash(key), key)) == null ? null : e.value;
                //    }
                //    final Node<K,V> getNode(int hash, Object key) {
                //        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
                          /** 1.对table进行校验：table不为空 && table长度大于0 &&
                                table索引位置(使用table.length - 1和hash值进行位与运算)的节点不为空 */
                //        if ((tab = table) != null && (n = tab.length) > 0 &&
                //                (first = tab[(n - 1) & hash]) != null) {
                              /** 2.检查first节点的hash值和key是否和入参的一样，如果一样则first即为目标节点，直接返回first节点 */
                //            if (first.hash == hash && // always check first node
                //                    ((k = first.key) == key || (key != null && key.equals(k))))
                //                return first;
                              /** 3.如果first不是目标节点，并且first的next节点不为空则继续遍历 */
                //            if ((e = first.next) != null) {
                //                if (first instanceof TreeNode)
                                      /** 4.如果是红黑树节点，则调用红黑树的查找目标节点方法getTreeNode */
                //                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //                do {
                                      /** 5.执行链表节点的查找，向下遍历链表, 直至找到节点的key和入参的key相等时,返回该节点 */
                //                    if (e.hash == hash &&
                //                            ((k = e.key) == key || (key != null && key.equals(k))))
                //                        return e;
                //                } while ((e = e.next) != null);
                //            }
                //        }
                          /**  6.找不到符合的返回空 */
                //        return null;
                //    }

                /** 代码块1-1：getTreeNode 获取红黑树节点 */
                    //    final TreeNode<K,V> getTreeNode(int h, Object k) {
                              /** 1.首先找到红黑树的根节点；2.使用根节点调用find方法 */
                    //        return ((parent != null) ? root() : this).find(h, k, null);
                    //    }

                /** 代码块1-2：find 红黑树查找 */
                    /*
                     * 从调用此方法的节点开始查找, 通过hash值和key找到对应的节点
                     * 此方法是红黑树节点的查找, 红黑树是特殊的自平衡二叉查找树
                     * 平衡二叉查找树的特点：左节点<根节点<右节点
                     */
                    //    final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
                              /** 1.将p节点赋值为调用此方法的节点，即为红黑树根节点 */
                    //        TreeNode<K,V> p = this;
                              /** 2.从p节点开始向下遍历 */
                    //        do {
                    //            int ph, dir; K pk;
                    //            TreeNode<K,V> pl = p.left, pr = p.right, q;
                                  /** 3.如果传入的hash值小于p节点的hash值，则往p节点的左边遍历 */
                    //            if ((ph = p.hash) > h)
                    //                p = pl;
                                  /** 4.如果传入的hash值大于p节点的hash值，则往p节点的右边遍历 */
                    //            else if (ph < h)
                    //                p = pr;
                                  /** 5.如果传入的hash值和key值等于p节点的hash值和key值,则p节点为目标节点,返回p节点 */
                    //            else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    //                return p;
                                  /** 6.p节点的左节点为空则将向右遍历 */
                    //            else if (pl == null)
                    //                p = pr;
                                  /** 7.p节点的右节点为空则向左遍历 */
                    //            else if (pr == null)
                    //                p = pl;
                                  /** 8.将p节点与k进行比较 */
                    //            else if ((kc != null ||
                                          /** 8.1 kc不为空代表k实现了Comparable */
                    //                    (kc = comparableClassFor(k)) != null) &&
                                          /** 8.2 k<pk则dir<0, k>pk则dir>0 */
                    //                    (dir = compareComparables(kc, k, pk)) != 0)
                                      /** 8.3 k<pk则向左遍历(p赋值为p的左节点), 否则向右遍历 */
                    //                p = (dir < 0) ? pl : pr;
                                  /** 9.代码走到此处, 代表key所属类没有实现Comparable, 直接指定向p的右边遍历 */
                    //            else if ((q = pr.find(h, k, kc)) != null)
                    //                return q;
                                  /** 10.代码走到此处代表“pr.find(h, k, kc)”为空, 因此直接向左遍历 */
                    //            else
                    //                p = pl;
                    //        } while (p != null);
                    //        return null;
                    //    }

                /** 代码块1-3：comparableClassFor 判断key是否实现了Comparable */
                    //    static Class<?> comparableClassFor(Object x) {
                              /** 1.判断x是否实现了Comparable接口 */
                    //        if (x instanceof Comparable) {
                    //            Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
                                  /** 2.校验x是否为String类型 */
                    //            if ((c = x.getClass()) == String.class) // bypass checks
                    //                return c;
                    //            if ((ts = c.getGenericInterfaces()) != null) {
                                      /** 3.遍历x实现的所有接口 */
                    //                for (int i = 0; i < ts.length; ++i) {
                                          /** 4.如果x实现了Comparable接口，则返回x的Class */
                    //                    if (((t = ts[i]) instanceof ParameterizedType) &&
                    //                            ((p = (ParameterizedType)t).getRawType() ==
                    //                                    Comparable.class) &&
                    //                            (as = p.getActualTypeArguments()) != null &&
                    //                            as.length == 1 && as[0] == c) // type arg is c
                    //                        return c;
                    //                }
                    //            }
                    //        }
                    //        return null;
                    //    }


            /** (2)、存储数据  put -> putVal */
                //    public V put(K key, V value) {
                //        // 对key的hashCode()做hash
                          /** onlyIfAbsent 为 false 表示， 如果放置的元素已经存在， 就予以替换 */
                //        return putVal(hash(key), key, value, false, true);
                //    }
                      /** 存储数据的核心方法-重要-理解每一步 */
                //    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
                          /* 定义一个数组tab，一个链表p，n永远存放数组长度，i用于存放key的hash计算后的值，即key在数组中的索引  */
                //        HashMap.Node[] tab; Object p; int n, i;
                          /** 1、校验table是否为空或者length等于0，如果是则调用resize方法进行初始化 */
                //        if ((tab = this.table) == null || (n = tab.length) == 0) {
                //            n = (tab = this.resize()).length;
                //        }
                          /** 2、通过hash值计算索引位置，将该索引位置的头节点赋值给p，如果p为空则直接在该索引位置新增一个节点即可 */
                //        if ((p = tab[i = n - 1 & hash]) == null) {
                //            tab[i] = this.newNode(hash, key, value, (HashMap.Node)null);
                          /* 该索引有数据存在 */
                //        } else {
                              /* 重新定义一个Node，和一个k */
                //            Object e;
                //            Object k;
                              /** 3.判断p节点的key和hash值是否跟传入的相等，如果相等, 则p节点即为要查找的目标节点，将p节点赋值给e节点 */
                //            if (((HashMap.Node)p).hash == hash && ((k = ((HashMap.Node)p).key) == key || key != null && key.equals(k))) {
                //                e = p;
                              /** 4.判断p节点是否为TreeNode, 如果是则调用红黑树的putTreeVal方法查找目标节点 */
                //            } else if (p instanceof HashMap.TreeNode) {
                                  /* 进行红黑树插值法,写入数据 */
                //                e = ((HashMap.TreeNode)p).putTreeVal(this, tab, hash, key, value);
                //            } else {
                                  /* 定义循环计数器 */
                //                int binCount = 0;
                                  /** 5.走到这代表p节点为普通链表节点，则调用普通的链表方法进行查找，使用binCount统计链表的节点数 */
                //                while(true) {
                                      /** 6.如果p的next节点为空时，则代表找不到目标节点，则新增一个节点并插入链表尾部 */
                //                    if ((e = ((HashMap.Node)p).next) == null) {
                //                        ((HashMap.Node)p).next = this.newNode(hash, key, value, (HashMap.Node)null);
                                          /** 7.校验节点数是否超过8个，如果超过则调用treeifyBin方法将链表节点转为红黑树节点，
                                                减一是因为循环是从p节点的下一个节点开始的 */
                //                        if (binCount >= 7) {
                                              /* 链表转换为红黑树 */
                //                            this.treeifyBin(tab, hash);
                //                        }
                //                        break;
                //                    }
                                      /** 8.如果e节点存在hash值和key值都与传入的相同，则e节点即为目标节点，跳出循环 */
                //                    if (((HashMap.Node)e).hash == hash && ((k = ((HashMap.Node)e).key) == key || key != null && key.equals(k))) {
                //                        break;
                //                    }
                //                    p = e;
                //                    ++binCount;
                //                }
                //            }
                              /** 9.如果e节点不为空，则代表目标节点存在，使用传入的value覆盖该节点的value，并返回oldValue */
                //            if (e != null) {
                //                V oldValue = ((HashMap.Node)e).value;
                //                if (!onlyIfAbsent || oldValue == null) {
                //                    ((HashMap.Node)e).value = value;
                //                }
                //                this.afterNodeAccess((HashMap.Node)e); // 用于LinkedHashMap
                //                return oldValue;
                //            }
                //        }
                //        ++this.modCount;
                          /** 10.如果插入节点后节点数超过阈值，则调用resize方法进行扩容 */
                //        if (++this.size > this.threshold) {
                //            this.resize();
                //        }
                //        this.afterNodeInsertion(evict); // 用于LinkedHashMap
                //        return null;
                //    }

                /** 代码块2-1：putTreeVal 红黑树的put操作，红黑树插入会同时维护原来的链表属性, 即原来的next属性 */
                    //    final HashMap.TreeNode<K, V> putTreeVal(HashMap<K, V> map, HashMap.Node<K, V>[] tab, int h, K k, V v) {
                    //        Class<?> kc = null;
                    //        boolean searched = false;
                              /** 1.查找根节点, 索引位置的头节点并不一定为红黑树的根节点 */
                    //        HashMap.TreeNode<K, V> root = this.parent != null ? this.root() : this;
                    //        HashMap.TreeNode p = root;
                    //
                    //        int dir;
                    //        HashMap.TreeNode q;
                    //        do {
                                /** 2.第一次进入，将根节点赋值给p节点，开始进行查找
                                        第二次开始根据dir获取p节点的左或右 */
                    //            int ph;
                                  /** 3.如果传入的hash值小于p节点的hash值，将dir赋值为-1，代表向p的左边查找树 */
                    //            if ((ph = p.hash) > h) {
                    //                dir = -1;
                                  /** 4.如果传入的hash值大于p节点的hash值， 将dir赋值为1，代表向p的右边查找树 */
                    //            } else if (ph < h) {
                    //                dir = 1;
                    //            } else {
                    //                Object pk;
                                      /** 5.如果传入的hash值和key值等于p节点的hash值和key值, 则p节点即为目标节点, 返回p节 */
                    //                if ((pk = p.key) == k || k != null && k.equals(pk)) {
                    //                    return p;
                    //                }
                                      /** 6.如果k所属的类没有实现Comparable接口 或者 k和p节点的key相等 */
                    //                if (kc == null && (kc = HashMap.comparableClassFor(k)) == null || (dir = HashMap.compareComparables(kc, k, pk)) == 0) {
                                          /** 6.1 第一次符合条件, 从p节点的左节点和右节点分别调用find方法进行查找, 如果查找到目标节点则返回 */
                    //                    if (!searched) {
                    //                        searched = true;
                    //                        HashMap.TreeNode ch;
                    //                        if ((ch = p.left) != null && (q = ch.find(h, k, kc)) != null || (ch = p.right) != null && (q = ch.find(h, k, kc)) != null) {
                    //                            return q;
                    //                        }
                    //                    }
                                          /** 6.2 否则使用定义的一套规则来比较k和p节点的key的大小, 用来决定向左还是向右查找
                                                (dir<0则代表k<pk，则向p左边查找；反之亦然) */
                    //                    dir = tieBreakOrder(k, pk);
                    //                }
                    //            }
                                  /** q赋值为x的父节点,中间变量,用于下面给x的父节点赋值 */
                    //            q = p;
                    //        } while((p = dir <= 0 ? p.left : p.right) != null);
                              /** 7.走进来代表已经找到x的位置，只需将x放到该位置即可 */
                    //        HashMap.Node<K, V> xpn = q.next;
                              /** 8.创建新的节点, 其中x的next节点为xpn, 即将x节点插入q与xpn之间 */
                    //        HashMap.TreeNode<K, V> x = map.newTreeNode(h, k, v, xpn);
                              /** 9.调整x、q、xpn之间的属性关系，如果时dir <= 0, 则代表x节点为q的左节点 */
                    //        if (dir <= 0) {
                    //            q.left = x;
                    //        } else {
                                  /** 如果时dir> 0, 则代表x节点为q的右节点 */
                    //            q.right = x;
                    //        }
                    //
                    //        q.next = x; // 将q的next节点设置为x
                    //        x.parent = x.prev = q; // 将x的parent和prev节点设置为q
                              /** 10.如果xpn不为空,则将xpn的prev节点设置为x节点,与上文的x节点的next节点对应 */
                    //        if (xpn != null) {
                    //            ((HashMap.TreeNode)xpn).prev = x;
                    //        }
                              /** 11.进行红黑树的插入平衡调整（红变黑、黑变红） */
                    //        moveRootToFront(tab, balanceInsertion(root, x));
                    //        return null;
                    //    }

                /** 代码块2-2：tieBreakOrder 用于不可比较或者hashCode相同时进行比较的方法, 只是一个一致的插入规则，用来维护重定位的等价性。 */
                    //    static int tieBreakOrder(Object a, Object b) {
                    //        int d;
                    //        if (a == null || b == null ||
                    //                (d = a.getClass().getName().
                    //                        compareTo(b.getClass().getName())) == 0)
                    //            d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
                    //                    -1 : 1);
                    //        return d;
                    //    }

                /** 代码块2-3 treeifyBin 将链表节点转为红黑树节点 */
                    //    final void treeifyBin(HashMap.Node<K, V>[] tab, int hash) {
                    //        int n;
                              /** 1.判断当前哈希值存储桶的长度是否大于64 */
                    //        if (tab != null && (n = tab.length) >= 64) {
                                  /** 1.1 大于64，将链表转化成红黑树 */
                    //            int index;
                    //            HashMap.Node e;
                                  /** 2.根据hash值计算索引值，将该索引位置的节点赋值给e，从e开始遍历该索引位置的链表 */
                    //            if ((e = tab[index = n - 1 & hash]) != null) {
                    //                HashMap.TreeNode<K, V> hd = null;
                    //                HashMap.TreeNode tl = null;
                    //                do {
                                          /** 3.将链表节点转红黑树节点 */
                    //                    HashMap.TreeNode<K, V> p = this.replacementTreeNode(e, (HashMap.Node)null);
                                          /** 4.如果是第一次遍历（tl为空代表为第一次循环），将头节点赋值给hd */
                    //                    if (tl == null) {
                    //                        hd = p;
                    //                    } else {
                                              /** 5.如果不是第一次遍历，则处理当前节点的prev属性和上一个节点的next属性 */
                    //                        p.prev = tl; // 当前节点的prev属性设为上一个节点
                    //                        tl.next = p; // 上一个节点的next属性设置为当前节点
                    //                    }
                                          /** 6.将p节点赋值给tl，用于在下一次循环中作为上一个节点进行一些链表的关联操作（p.prev = tl 和 tl.next = p） */
                    //                    tl = p;
                    //                } while((e = e.next) != null);
                                      /** 7.将table该索引位置赋值为新转的TreeNode的头节点，如果该节点不为空，则以以头节点(hd)为根节点, 构建红黑树 */
                    //                if ((tab[index] = hd) != null) {
                    //                    hd.treeify(tab);
                    //                }
                    //            }
                    //        } else {
                                  /** 1.2 如果table为空或者table的长度小于64, 调用resize方法进行扩容 */
                    //            this.resize();
                    //        }
                    //
                    //    }

                /** 代码块2-4 treeify 构建红黑树 */
                    //    final void treeify(HashMap.Node<K, V>[] tab) {
                    //        HashMap.TreeNode<K, V> root = null;
                    //        HashMap.TreeNode next;
                              /** 1.将调用此方法的节点赋值给x，以x作为起点，开始进行遍历 */
                    //        for(HashMap.TreeNode x = this; x != null; x = next) {
                                  /** 1.1 next赋值为x的下个节点 */
                    //            next = (HashMap.TreeNode)x.next;
                                  /** 1.2 将x的左右节点设置为空 */
                    //            x.left = x.right = null;
                                  /** 2.如果还没有根节点, 则将x设置为根节点 */
                    //            if (root == null) {
                                      /** 2.1 根节点没有父节点 */
                    //                x.parent = null;
                                      /** 2.2 根节点必须为黑色 */
                    //                x.red = false;
                                      /** 2.3 将x设置为根节点 */
                    //                root = x;
                                  /** 3.存在根节点 */
                    //            } else {
                                      /** 3.1 k赋值为x的key */
                    //                K k = x.key;
                                      /** 3.2 h赋值为x的hash值 */
                    //                int h = x.hash;
                    //                Class<?> kc = null;
                    //                HashMap.TreeNode p = root;
                    //
                    //                int dir;
                    //                HashMap.TreeNode xp;
                    //                do {
                    //                    K pk = p.key;
                    //                    int ph;
                                          /** 4.如果x节点的hash值小于p节点的hash值，则将dir赋值为-1, 代表向p的左边查找 */
                    //                    if ((ph = p.hash) > h) {
                    //                        dir = -1;
                                          /** 5.如果x节点的hash值大于p节点的hash值，则将dir赋值为1, 代表向p的右边查找 */
                    //                    } else if (ph < h) {
                    //                        dir = 1;
                                          /** 6.走到这代表x的hash值和p的hash值相等，则比较key值 */
                    //                    } else if (kc == null &&
                                                /** 6.1 如果k没有实现Comparable接口 或者 x节点的key和p节点的key相等 */
                    //                          (kc = HashMap.comparableClassFor(k)) == null ||
                    //                          (dir = HashMap.compareComparables(kc, k, pk)) == 0) {
                                              /** 6.2 使用定义的一套规则来比较x节点和p节点的大小，用来决定向左还是向右查找 */
                    //                        dir = tieBreakOrder(k, pk);
                    //                    }
                                          /** 7.xp赋值为x的父节点,中间变量用于下面给x的父节点赋值 */
                    //                    xp = p;
                                      /** 根据dir设置左或右为下一个父节点，当p==null时，代表该位置即为x的目标位置 */
                    //                } while((p = dir <= 0 ? p.left : p.right) != null);
                                      /** 8.x的父节点即为最后一次遍历的p节点 */
                    //                x.parent = xp;
                                      /** 9.如果时dir <= 0, 则代表x节点为父节点的左节点 */
                    //                if (dir <= 0) {
                    //                    xp.left = x;
                                      /** 10.如果时dir > 0, 则代表x节点为父节点的右节点 */
                    //                } else {
                    //                    xp.right = x;
                    //                }
                                      /** 11.进行红黑树的插入平衡(通过左旋、右旋和改变节点颜色来保证当前树符合红黑树的要求) */
                    //                root = balanceInsertion(root, x);
                    //            }
                    //        }
                              /** 12.如果root节点不在table索引位置的头节点, 则将其调整为头节点 */
                    //        moveRootToFront(tab, root);
                    //    }

                /** 代码块2-5 moveRootToFront 将root放到头节点的位置 */
                    /* 如果当前索引位置的头节点不是root节点, 则将root的上一个节点和下一个节点进行关联,
                        将root放到头节点的位置, 原头节点放在root的next节点上 */
                    //    static <K, V> void moveRootToFront(HashMap.Node<K, V>[] tab, HashMap.TreeNode<K, V> root) {
                    //        int n;
                              /** 1.校验root是否为空、table是否为空、table的length是否大于0 */
                    //        if (root != null && tab != null && (n = tab.length) > 0) {
                                  /** 2.计算root节点的索引位置 */
                    //            int index = n - 1 & root.hash;
                    //            HashMap.TreeNode<K, V> first = (HashMap.TreeNode)tab[index];
                                  /** 3.如果该索引位置的头节点不是root节点，则该索引位置的头节点替换为root节点 */
                    //            if (root != first) {
                                      /** 3.1 将该索引位置的头节点赋值为root节点，操作双向链表 */
                    //                tab[index] = root;
                    //                HashMap.TreeNode<K, V> rp = root.prev; // root节点的上一个节点
                    //                HashMap.Node rn;
                                      /** 3.2 和 3.3 两个操作是移除root节点的过程 */
                                      /** 3.2 如果root节点的next节点不为空，则将root节点的next节点的prev属性设置为root节点的prev节点，相当于把root从链表移除 */
                    //                if ((rn = root.next) != null) {
                    //                    ((HashMap.TreeNode)rn).prev = rp;
                    //                }
                                      /** 3.3 如果root节点的prev节点不为空，则将root节点的prev节点的next属性设置为root节点的next节点 */
                    //                if (rp != null) {
                    //                    rp.next = rn;
                    //                }
                                      /** 3.4 和 3.5 两个操作将first节点接到root节点后面 */
                                      /** 3.4 如果原头节点不为空, 则将原头节点的prev属性设置为root节点，相当于root目前位于链表的首位 */
                    //                if (first != null) {
                    //                    first.prev = root;
                    //                }
                                      /** 3.5 将root节点的next属性设置为原头节点，原来的第一个节点现在作为root的下一个节点，变成了第二个节点 */
                    //                root.next = first;
                                      /** 3.6 root此时已经被放到该位置的头节点位置，因此将prev属性设为空 */
                    //                root.prev = null;
                    //            }
                                  /** 4.检查树是否正常 */
                    //            assert checkInvariants(root);
                    //        }
                    //
                    //    }

                /** (3)、扩容方法  resize */
                    //    final HashMap.Node<K, V>[] resize() {
                    //        HashMap.Node<K, V>[] oldTab = this.table;
                    //        int oldCap = oldTab == null ? 0 : oldTab.length;
                    //        int oldThr = this.threshold;
                    //        int newThr = 0;
                    //        int newCap;
                              /** 1.老表的容量不为0，即老表不为空 */
                    //        if (oldCap > 0) {
                                 /** 1.1 判断老表的容量是否超过最大容量值：如果超过则将阈值设置为Integer.MAX_VALUE，并直接返回老表,
                                    此时oldCap * 2比Integer.MAX_VALUE大，因此无法进行重新分布，只是单纯的将阈值扩容到最大 */
                    //            if (oldCap >= 1073741824) {
                    //                this.threshold = 2147483647;
                    //                return oldTab;
                    //            }
                                  /** 1.2 将newCap赋值为oldCap的2倍(<<)，如果newCap<最大容量并且oldCap>=16, 则将新阈值设置为原来的两倍 */
                    //            if ((newCap = oldCap << 1) < 1073741824 && oldCap >= 16) {
                    //                newThr = oldThr << 1;
                    //            }
                              /** 2.如果老表的容量为0, 老表的阈值大于0, 是因为初始容量被放入阈值，则将新表的容量设置为老表的阈值 */
                    //        } else if (oldThr > 0) {
                    //            newCap = oldThr;
                    //        } else {
                                  /** 3.老表的容量为0, 老表的阈值为0，这种情况是没有传初始容量的new方法创建的空表，将阈值和容量设置为默认值 加载因子0.75 * 16 = 12 */
                    //            newCap = 16;
                    //            newThr = 12;
                    //        }
                              /** 4.如果新表的阈值为空, 则通过新的容量*负载因子获得阈值 */
                    //        if (newThr == 0) {
                    //            float ft = (float)newCap * this.loadFactor;
                    //            newThr = newCap < 1073741824 && ft < 1.07374182E9F ? (int)ft : 2147483647;
                    //        }
                    //
                              /** 5.将当前阈值设置为刚计算出来的新的阈值，定义新表，容量为刚计算出来的新容量，将table设置为新定义的表。 */
                    //        this.threshold = newThr;
                    //        HashMap.Node<K, V>[] newTab = new HashMap.Node[newCap];
                    //        this.table = newTab;
                              /** 6.如果老表不为空，则需遍历所有节点，将节点赋值给新表 */
                    //        if (oldTab != null) {
                    //            for(int j = 0; j < oldCap; ++j) {
                    //                HashMap.Node e;
                    //                if ((e = oldTab[j]) != null) { // 将索引值为j的老表头节点赋值给e
                    //                    oldTab[j] = null; // 将老表的节点设置为空, 以便垃圾收集器回收空间
                                          /** 7.如果e.next为空, 则代表老表的该位置只有1个节点，计算新表的索引位置, 直接将该节点放在该位置 */
                    //                    if (e.next == null) {
                    //                        newTab[e.hash & newCap - 1] = e;
                                          /** 8.如果是红黑树节点，则进行红黑树的重hash分布(跟链表的hash分布基本相同)
                                                分割树，将新表和旧表分割成两个树，并判断索引处节点的长度是否需要转换成红黑树放入新表存储 */
                    //                    } else if (e instanceof HashMap.TreeNode) {
                    //                        ((HashMap.TreeNode)e).split(this, newTab, j, oldCap);
                    //                    } else {
                                              /** 9.如果是普通的链表节点，则进行普通的重hash分布 */
                    //                        HashMap.Node<K, V> loHead = null; // 存储索引位置为:“原索引位置”的头节点
                    //                        HashMap.Node<K, V> loTail = null; // 存储索引位置为:“原索引位置”的子节点
                    //                        HashMap.Node<K, V> hiHead = null; // 存储索引位置为:“原索引位置+oldCap”的头节点
                    //                        HashMap.Node hiTail = null;       // 存储索引位置为:“原索引位置+oldCap”的子节点
                    //
                    //                        HashMap.Node next;
                    //                        do {
                                                  /** 获取上一个节点的Next */
                    //                            next = e.next;
                                                  /** 9.1 如果e的hash值与老表的容量进行与运算为0,则扩容后的索引位置跟老表的索引位置一样 */
                    //                            if ((e.hash & oldCap) == 0) {
                                                      /** 9.1.1 如果loTail为空, 代表该节点为第一个节点，将loHead赋值为第一个节点 */
                    //                                if (loTail == null) {
                    //                                    loHead = e;
                                                      /** 9.1.2 如果loTail不为空，将节点添加在loTail后面 */
                    //                                } else {
                    //                                    loTail.next = e;
                    //                                }
                                                      /** 9.1.3 将loTail赋值为新增的节点 */
                    //                                loTail = e;
                                                  /** 9.2 如果e的hash值与老表的容量进行与运算为1,则扩容后的索引位置为:老表的索引位置＋oldCap */
                    //                            } else {
                                                      /** 9.2.1 如果hiTail为空, 代表该节点为第一个节点，将hiHead赋值为第一个节点 */
                    //                                if (hiTail == null) {
                    //                                    hiHead = e;
                                                      /** 9.2.2 如果hiTail不为空, 将节点添加在hiTail后面 */
                    //                                } else {
                    //                                    hiTail.next = e;
                    //                                }
                                                      /** 9.2.3 将hiTail赋值为新增的节点 */
                    //                                hiTail = e;
                    //                            }
                                                  /** 循环的关键，当前节点设置为当前节点的Next */
                    //                            e = next;
                    //                        } while(next != null);
                                              /** 10.如果loTail不为空（说明老表的数据有分布到新表上“原索引位置”的节点），则将最后一个节点
                                                   的next设为空，并将新表上索引位置为“原索引位置”的节点设置为对应的头节点 */
                    //                        if (loTail != null) {
                    //                            loTail.next = null;
                    //                            newTab[j] = loHead;
                    //                        }
                                              /** 11.如果hiTail不为空（说明老表的数据有分布到新表上“原索引+oldCap位置”的节点），则将最后
                                                  一个节点的next设为空，并将新表上索引位置为“原索引+oldCap”的节点设置为对应的头节点 */
                    //                        if (hiTail != null) {
                    //                            hiTail.next = null;
                    //                            newTab[j + oldCap] = hiHead;
                    //                        }
                    //                    }
                    //                }
                    //            }
                    //        }
                              /** 12.返回新表 */
                    //        return newTab;
                    //    }

                /** 代码块3-1 split 扩容后，红黑树的hash分布，只可能存在于两个位置：原索引位置、原索引位置+oldCap */
                    //    final void split(HashMap<K, V> map, HashMap.Node<K, V>[] tab, int index, int bit) {
                    //        HashMap.TreeNode<K, V> loHead = null; // 存储索引位置为:“原索引位置”的节点
                    //        HashMap.TreeNode<K, V> loTail = null;
                    //        HashMap.TreeNode<K, V> hiHead = null; // 存储索引位置为:“原索引+oldCap”的节点
                    //        HashMap.TreeNode<K, V> hiTail = null;
                    //        int lc = 0;
                    //        int hc = 0;
                    //
                    //        HashMap.TreeNode next;
                              /** 1.以调用此方法的节点开始，遍历整个红黑树节点 */
                    //        for(HashMap.TreeNode e = this; e != null; e = next) {
                                  /** 1.1 next赋值为e的下个节点 */
                    //            next = (HashMap.TreeNode)e.next;
                                  /** 1.2 同时将老表的节点设置为空，以便垃圾收集器回收 */
                    //            e.next = null;
                                  /** 2.如果e的hash值与老表的容量进行与运算为0,则扩容后的索引位置跟老表的索引位置一样 */
                    //            if ((e.hash & bit) == 0) {
                                      /** 2.1 如果loTail为空, 代表该节点为第一个节点，将loHead赋值为第一个节点 */
                    //                if ((e.prev = loTail) == null) {
                    //                    loHead = e;
                    //                } else {
                                          /** 2.2 不为空，将节点添加在loTail后面 */
                    //                    loTail.next = e;
                    //                }
                                      /** 2.3 将loTail赋值为新增的节点 */
                    //                loTail = e;
                                      /** 2.4 统计原索引位置的节点个数*/
                    //                ++lc;
                                  /** 3.如果e的hash值与老表的容量进行与运算为1,则扩容后的索引位置为:老表的索引位置＋oldCap */
                    //            } else {
                                      /** 3.1 如果hiHead为空, 代表该节点为第一个节点，将hiHead赋值为第一个节点 */
                    //                if ((e.prev = hiTail) == null) {
                    //                    hiHead = e;
                    //                } else {
                                          /** 3.2 不为空，将节点添加在hiTail后面 */
                    //                    hiTail.next = e;
                    //                }
                                      /** 3.3 将hiTail赋值为新增的节点 */
                    //                hiTail = e;
                                      /** 3.4 统计索引位置为原索引+oldCap的节点个数 */
                    //                ++hc;
                    //            }
                    //        }
                              /** 4.如果原索引位置的节点不为空 */
                    //        if (loHead != null) {
                                  /** 4.1 如果节点个数<=6个则将红黑树转为链表结构 */
                    //            if (lc <= 6) {
                    //                tab[index] = loHead.untreeify(map);
                    //            } else {
                                      /** 4.2 将原索引位置的节点设置为对应的头节点 */
                    //                tab[index] = loHead;
                                      /** 4.3 如果hiHead不为空，则代表原来的红黑树(老表的红黑树由于节点被分到两个位置)
                                          已经被改变, 需要重新构建新的红黑树 */
                    //                if (hiHead != null) {
                                          /** 4.4 以loHead为根节点, 构建新的红黑树 */
                    //                    loHead.treeify(tab);
                    //                }
                    //            }
                    //        }
                              /** 5.如果索引位置为原索引+oldCap的节点不为空 */
                    //        if (hiHead != null) {
                                  /** 5.1 如果节点个数<=6个则将红黑树转为链表结构 */
                    //            if (hc <= 6) {
                    //                tab[index + bit] = hiHead.untreeify(map);
                    //            } else {
                                      /** 5.2 将索引位置为原索引+oldCap的节点设置为对应的头节点 */
                    //                tab[index + bit] = hiHead;
                                      /** 5.3 loHead不为空则代表原来的红黑树(老表的红黑树由于节点被分到两个位置)
                                          已经被改变, 需要重新构建新的红黑树 */
                    //                if (loHead != null) {
                                          /** 5.4 以hiHead为根节点, 构建新的红黑树 */
                    //                    hiHead.treeify(tab);
                    //                }
                    //            }
                    //        }
                    //
                    //    }

                /** 代码块3-2 untreeify 将红黑树节点转为链表节点, 当节点<=6个时会被触发 */
                    //    final HashMap.Node<K, V> untreeify(HashMap<K, V> map) {
                              /** 声明变量：hd指向头节点 */
                    //        HashMap.Node<K, V> hd = null;
                              /** 声明变量：tl指向尾节点 */
                    //        HashMap.Node<K, V> tl = null;
                              /** 1.从调用该方法的节点, 即链表的头节点开始遍历, 将所有节点全转为链表节点 */
                    //        for(Object q = this; q != null; q = ((HashMap.Node)q).next) {
                                  /** 2.调用replacementNode方法构建链表节点 */
                    //            HashMap.Node<K, V> p = map.replacementNode((HashMap.Node)q, (HashMap.Node)null);
                                  /** 3.如果tl为null, 则代表当前节点为第一个节点, 将hd赋值为该节点 */
                    //            if (tl == null) {
                    //                hd = p;
                    //            } else {
                                      /** 4.否则, 将尾节点的next属性设置为当前节点p */
                    //                tl.next = p;
                    //            }
                                  /** 5.每次都将tl节点指向当前节点, 即尾节点 */
                    //            tl = p;
                    //        }
                              /** 6.返回转换后的链表的头节点 */
                    //        return hd;
                    //    }

                /** (4)、删除数据  remove -> removeNode */
                    //    public final void remove() {
                              /** 移除某个节点 */
                    //        HashMap.Node<K, V> p = this.current;
                    //        if (p == null) {
                    //            throw new IllegalStateException();
                    //        } else if (HashMap.this.modCount != this.expectedModCount) {
                                  /** 注意：此处存在坑，如果遍历时，删除数据会抛出异常 fast-fail */
                    //            throw new ConcurrentModificationException();
                    //        } else {
                    //            this.current = null;
                    //            HashMap.this.removeNode(p.hash, p.key, (Object)null, false, false);
                    //            this.expectedModCount = HashMap.this.modCount;
                    //        }
                    //    }
                            /**
                             * 删除节点
                             * 描述：
                             *      方法为final，不可被覆写，子类可以通过实现afterNodeRemoval方法增加自己的处理逻辑
                             * 入参：
                             *      hash：key的hash值，该值通过hash(key)获取
                             *      key：要删除的键值对的key
                             *      value：要删除的键值对的value,该值是否作为删除的条件取决于matchValue是否为true
                             *      matchValue：如果为true，则当key对应的键值对的值equals(value)为true时才能删除，否则不关心value的值
                             *      movable：删除后是否移动节点，如果为false，则不移动
                             *  返回：
                             *      返回被删除的节点对象，如果没有删除任何节点则返回NULL
                             */
                    //      final HashMap.Node<K, V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
                    //          HashMap.Node[] tab;
                    //          HashMap.Node p;
                    //          int n;
                    //          int index;
                                /** 1.如果table不为空并且根据hash值计算出来的索引位置不为空, 将该位置的节点赋值给p */
                    //          if ((tab = this.table) != null && (n = tab.length) > 0 && (p = tab[index = n - 1 & hash]) != null) {
                    //              HashMap.Node<K, V> node = null;
                    //              Object k;
                                    /** 2.如果p的hash值和key都与入参的相同, 则p即为目标节点, 赋值给node(根节点) */
                    //              if (p.hash == hash && ((k = p.key) == key || key != null && key.equals(k))) {
                    //                  node = p;
                                    /** 3.否则将p.next赋值给e，向下遍历节点 */
                    //              } else {
                    //                  HashMap.Node e;
                    //                  if ((e = p.next) != null) {
                                            /** 3.1 如果p是TreeNode则调用红黑树的方法查找节点 */
                    //                      if (p instanceof HashMap.TreeNode) {
                    //                          node = ((HashMap.TreeNode)p).getTreeNode(hash, key);
                    //                      } else {
                                                /** 3.2 否则，进行普通链表节点的查找 */
                    //                          label88: {
                                                    /** 3.2.1 hash或key不想等，则继续循环，否则退出循环 */
                    //                              while(e.hash != hash || (k = e.key) != key && (key == null || !key.equals(k))) {
                                                        /** 3.2.2 记录最后一个不是的节点，用于下面删除节点 */
                    //                                  p = e;
                                                        /** 3.2.3 链表循环到最后，退出循环 */
                    //                                  if ((e = e.next) == null) {
                    //                                      break label88;
                    //                                  }
                    //                              }
                                                    /** 3.2.4 hash与key匹配，则e即为目标节点，复制给node */
                    //                              node = e;
                    //                          }
                    //                      }
                    //                  }
                    //              }
                    //              Object v;
                                    /** 4.如果node不为空(即根据传入key和hash值查找到目标节点)，则进行移除操作 */
                    //              if (node != null && (!matchValue || (v = ((HashMap.Node)node).value) == value || value != null && value.equals(v))) {
                                        /** 4.1 如果是TreeNode则调用红黑树的移除方法 */
                    //                  if (node instanceof HashMap.TreeNode) {
                    //                      ((HashMap.TreeNode)node).removeTreeNode(this, tab, movable);
                                        /** 4.2 如果node是该索引位置的头节点则直接将该索引位置的值赋值为node的next节点，
                                            “node == p”只会出现在node是头节点的时候，如果node不是头节点，则node为p的next节点 */
                    //                  } else if (node == p) {
                    //                      tab[index] = ((HashMap.Node)node).next;
                    //                  } else {
                                            /** 4.3 否则将node的上一个节点的next属性设置为node的next节点,
                                                即将node节点移除, 将node的上下节点进行关联(链表的移除) */
                    //                      p.next = ((HashMap.Node)node).next;
                    //                  }
                    //                  ++this.modCount;
                    //                  --this.size;
                    //                  this.afterNodeRemoval((HashMap.Node)node); // 供LinkedHashMap使用
                                        /** 5.返回被移除的节点 */
                    //                  return (HashMap.Node)node;
                    //              }
                    //          }
                    //
                    //          return null;
                    //      }

                    /**
                     * 代码块4-1 removeTreeNode 红黑树的节点移除
                     * 入参：
                     *      map：要移除的节点
                     *      tab：哈希值存储桶
                     *      movable：删除后是否移动节点，如果为false，则不移动
                     */
                        //    final void removeTreeNode(HashMap<K, V> map, HashMap.Node<K, V>[] tab, boolean movable) {
                                  /** --- 链表的处理start --- */
                        //        int n;
                                  /** 1.table不为空且length为0，进行节点删除 */
                        //        if (tab != null && (n = tab.length) != 0) {
                                      /** 2.根据hash计算出索引的位置 */
                        //            int index = n - 1 & this.hash;
                                      /** 3.将索引位置的头节点赋值给first和root */
                        //            HashMap.TreeNode<K, V> first = (HashMap.TreeNode)tab[index];
                        //            HashMap.TreeNode<K, V> root = first;
                                      /** 4.该方法被将要被移除的node(TreeNode)调用, 因此此方法的this为要被移除node节点,
                                          将node的next节点赋值给succ节点，prev节点赋值给pred节点 */
                        //            HashMap.TreeNode<K, V> succ = (HashMap.TreeNode)this.next;
                        //            HashMap.TreeNode<K, V> pred = this.prev;
                                      /** 5.如果pred节点为空，则代表要被移除的node节点为头节点，
                                          则将table索引位置的值和first节点的值赋值为succ节点(node的next节点)即可 */
                        //            if (pred == null) {
                        //                first = succ;
                        //                tab[index] = succ;
                        //            } else {
                                          /** 6.否则将pred节点的next属性设置为succ节点(node的next节点) */
                        //                pred.next = succ;
                        //            }
                                      /** 7.如果succ节点不为空，则将succ的prev节点设置为pred, 与前面对应 */
                        //            if (succ != null) {
                        //                succ.prev = pred;
                        //            }
                                      /** --- 链表的处理end --- */

                                      /** --- 红黑树的处理start --- */
                                      /** 8.如果进行到此first节点为空，则代表该索引位置已经没有节点则直接返回 */
                        //            if (first != null) {
                                          /** 9.如果root的父节点不为空, 则将root赋值为根节点 */
                        //                if (root.parent != null) {
                        //                    root = root.root();
                        //                }
                        //                HashMap.TreeNode rl;
                                          /** 10.通过root节点来判断此红黑树是否太小, 如果是则调用untreeify方法转为链表节点并返回，否则继续执行红黑树处理 */
                        //                if (root != null && (!movable || root.right != null && (rl = root.left) != null && rl.left != null)) {
                                              /** 11.pl赋值为要被移除的node节点的左节点，pr赋值为要被移除的node节点的右节点 */
                        //                    HashMap.TreeNode<K, V> pl = this.left;
                        //                    HashMap.TreeNode<K, V> pr = this.right;
                        //                    HashMap.TreeNode replacement;
                        //                    HashMap.TreeNode s;
                        //                    HashMap.TreeNode pp;
                                              /** 12.如果p的左节点和右节点都不为空时 */
                        //                    if (pl != null && pr != null) {
                                                  /** 12.1 将s节点赋值为当前节点的右节点，向左一直查找，跳出循环时,s为没有左节点的节点 */
                        //                        for(s = pr; (pp = s.left) != null; s = pp) {
                        //                        }
                                                  /** 12.2 交换当前节点和s节点的颜色 */
                        //                        boolean c = s.red;
                        //                        s.red = this.red;
                        //                        this.red = c;
                                                  /** 12.3 设置sr为s的右节点 */
                        //                        HashMap.TreeNode<K, V> sr = s.right;
                                                  /** 12.4 设置pp为当前节点的父节点 */
                        //                        HashMap.TreeNode<K, V> pp = this.parent;
                                              /** ---第一次调整：将当前节点和s节点进行了位置调换--- */
                                                  /** 12.5 如果当前节点的右节点即为s节点，则将当前节点的父节点赋值为s，将s的右节点赋值为当前节点 */
                        //                        if (s == pr) {
                        //                            this.parent = s;
                        //                            s.right = this;
                        //                        } else {
                                                      /** 12.6 将sp赋值为s的父节点 */
                        //                            HashMap.TreeNode<K, V> sp = s.parent;
                                                      /** 12.7 将当前节点的父节点赋值为sp */
                        //                            if ((this.parent = sp) != null) {
                                                          /** 12.7.1 如果s节点为sp的左节点，则将sp的左节点赋值为当前节点 */
                        //                                if (s == sp.left) {
                        //                                    sp.left = this;
                        //                                } else {
                                                              /** 12.7.2 否则s节点为sp的右节点，则将sp的右节点赋值为当前节点 */
                        //                                    sp.right = this;
                        //                                }
                        //                            }
                                                      /** 12.8 s的右节点赋值为当前节点的右节点，且pr不为空 */
                        //                            if ((s.right = pr) != null) {
                                                          /** 12.8.1 将pr的父节点赋值为s */
                        //                                pr.parent = s;
                        //                            }
                        //                        }
                                              /** ---第二次调整--- */
                                                  /** 12.9 将当前节点的左节点赋值为空，pl已经保存了该节点 */
                        //                        this.left = null;
                                                  /** 12.10 将当前节点的右节点赋值为sr，如果sr不为空，则将sr的父节点赋值为当前节点 */
                        //                        if ((this.right = sr) != null) {
                        //                            sr.parent = this;
                        //                        }
                                                  /** 12.11 将s节点的左节点赋值为pl，如果pl不为空，则将pl的父节点赋值为s节点 */
                        //                        if ((s.left = pl) != null) {
                        //                            pl.parent = s;
                        //                        }
                                                  /** 12.12 将s的父节点赋值为当前节点的父节点pp
                                                        如果pp为空，则当前节点为root节点, 交换后s成为新的root节点 */
                        //                        if ((s.parent = pp) == null) {
                        //                            root = s;
                                                  /** 12.13 如果当前节点不为root节点, 并且当前节点是pp的左节点，则将pp的左节点赋值为s节点 */
                        //                        } else if (this == pp.left) {
                        //                            pp.left = s;
                        //                        } else {
                                                      /** 12.14 如果当前节点不为root节点, 并且当前节点是pp的右节点，则将pp的右节点赋值为s节点 */
                        //                            pp.right = s;
                        //                        }
                                                  /** 12.15.寻找replacement节点，用来替换掉当前节点
                                                        如果sr不为空，则replacement节点为sr，因为s没有左节点，所以使用s的右节点来替换当前节点的位置 */
                        //                        if (sr != null) {
                        //                            replacement = sr;
                        //                        } else {
                                                      /** 12.16 如果sr为空，则s为叶子节点，replacement为当前节点，只需要将当前节点直接去除即可 */
                        //                            replacement = this;
                        //                        }
                                              /** 13.承接第12点的判断，如果当前节点的左节点不为空，右节点为空，replacement节点为当前节点的左节点 */
                        //                    } else if (pl != null) {
                        //                        replacement = pl;
                                              /** 14.如果当前节点的右节点不为空,左节点为空，replacement节点为当前节点的右节点 */
                        //                    } else if (pr != null) {
                        //                        replacement = pr;
                                              /** 15.如果当前节点的左右节点都为空, 即当前节点为叶子节点, replacement节点为当前节点本身 */
                        //                    } else {
                        //                        replacement = this;
                        //                    }
                                          /** ---第三次调整--- */
                                              /** 16.如果当前节点不是叶子节点，使用replacement节点替换掉当前节点的位置，将当前节点移除 */
                        //                    if (replacement != this) { //
                                                  /** 16.1 将当前节点的父节点赋值给replacement节点的父节点, 同时赋值给s节点 */
                        //                        s = replacement.parent = this.parent;
                                                  /** 16.2 如果当前没有父节点, 即当前节点为root节点，则将root节点赋值为replacement节点即可 */
                        //                        if (s == null) {
                        //                            root = replacement;
                                                  /** 16.3 如果当前节点不是root节点, 并且当前节点为s的左节点，则将s的左节点赋值为替换节点replacement */
                        //                        } else if (this == s.left) {
                        //                            s.left = replacement;
                                                  /** 16.4 如果当前节点不是root节点, 并且当前节点为s的右节点，则将s的右节点赋值为替换节点replacement */
                        //                        } else {
                        //                            s.right = replacement;
                        //                        }
                                                  /** 16.5 当前节点的位置已经被完整的替换为replacement, 将当前节点清空, 以便垃圾收集器回收 */
                        //                        this.left = this.right = this.parent = null;
                        //                    }
                                              /** 17.如果当前节点不为红色则进行红黑树删除平衡调整
                                                  (如果删除的节点是红色则不会破坏红黑树的平衡无需调整) */
                        //                    s = this.red ? root : balanceDeletion(root, replacement);
                                              /** 18.如果当前节点为叶子节点, 则简单的将当前节点去除即可 */
                        //                    if (replacement == this) {
                        //                        pp = this.parent;
                                                  /** 18.1 将当前节点的parent属性设置为空 */
                        //                        this.parent = null;
                        //                        if (pp != null) {
                                                      /** 18.2 如果当前节点为父节点的左节点，则将父节点的左节点赋值为空 */
                        //                            if (this == pp.left) {
                        //                                pp.left = null;
                                                      /** 18.3 如果当前节点为父节点的右节点， 则将父节点的右节点赋值为空 */
                        //                            } else if (this == pp.right) {
                        //                                pp.right = null;
                        //                            }
                        //                        }
                        //                    }
                                              /** 19.将root节点移到索引位置的头节点 */
                        //                    if (movable) {
                        //                        moveRootToFront(tab, s);
                        //                    }
                        //
                        //                } else {
                                              /** 20.承接第10点的判断，当红黑树过小时，进行红黑树转链表操作 */
                        //                    tab[index] = first.untreeify(map);
                        //                }
                        //            }
                                      /** --- 红黑树的处理end --- */
                        //        }
                        //    }

}
